class Solution {//leetcode300——最长递增子序列
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> cnt;
        cnt.push_back(nums[0]);
        int n=nums.size();
        for(int i=1;i<n;i++){
            if(nums[i]>cnt.back()) cnt.push_back(nums[i]);
            else {
                int left=0,right=cnt.size();
                while(left<right){
                    int mid=(right-left)/2+left;
                    if(cnt[mid]<nums[i]) left=mid+1;
                    else right=mid;
                }
                cnt[left]=nums[i];
            }
        }
        return cnt.size();
    }
};